import java.util.ArrayList;
import java.util.List;

/**
 * 输入： arr = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * @author leiwenkang <leiwenkang@kuaishou.com>
 * Created on 2023-07-31
 */
public class Study2 {

    public static void main(String[] args) {
        int[][] matrix = {{1, 3},{2,6},{8,10},{15,18}};
        List<int[]> res = mergeArray(matrix);
        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i)[0]);
            System.out.print(" ");
            System.out.print(res.get(i)[1]);
            System.out.println();
        }

    }

    public static List<int[]> mergeArray(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return null;
        }
        //按照数组第一个元素的大小升序
        sort(matrix);
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            if (list.isEmpty() || matrix[i][0] > list.get(list.size() - 1)[1]) {
                list.add(matrix[i]);
            } else { //合并
                int[] lastArr = list.get(list.size() - 1);
                lastArr[1] = Math.max(lastArr[1], matrix[i][1]);
            }
        }

        return list;
    }

    public static void sort(int[][] matrix) {
        quickSort(matrix, 0, matrix.length - 1);
    }

    public static void quickSort(int[][] matrix, int low, int high) {
        if (low >= high) {
            return;
        }
        int pos = partition(matrix, low, high);
        quickSort(matrix, low, pos - 1);
        quickSort(matrix, pos + 1, high);
    }

    public static int partition(int[][] matrix, int low, int high) {
        int[] val = matrix[low];
        while (low < high) {
            while (low < high && matrix[high][0] >= val[0]) {
               high--;
            }
            matrix[low] = matrix[high];

            while (low < high && matrix[low][0] <= val[0]) {
                low++;
            }
            matrix[high] = matrix[low];
        }

        matrix[low] = val;
        return low;
    }
}
